package com.github.hgkmail.hello.leetcode101.unionfind;

import com.github.hgkmail.hello.leetcode101.base.UnionFindEx;
import com.github.hgkmail.hello.leetcode101.base.UnionFindWithMap;

public class LC128LongestConsecutiveSequence {

    public int longestConsecutive(int[] nums) {
        //base
        if (nums.length<=0) {
            return 0;
        }
        UnionFindWithMap uf = new UnionFindWithMap(nums);
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (uf.parent.containsKey(num+1)) {
                uf.union(num, num+1);
            }
        }
        int maxSize = 0;
        for (int i = 0; i < nums.length; i++) {
            maxSize = Math.max(maxSize, uf.size.get(nums[i]));
        }
        return maxSize;
    }

    public static void main(String[] args) {
        System.out.println(new LC128LongestConsecutiveSequence().longestConsecutive(new int[]{0,-1}));
    }
}
